package com.jeff.practice;

import java.util.*;

/**
 * 消息：给定一棵二叉树，求二叉树的从根节点到叶子节点的值的最大和。
 *
 * @author yaojianfeng
 */
public class Test1 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        String[] strs = in.nextLine().split(" ");
        int[] nums = new int[strs.length];
        for (int i = 0; i < strs.length; i++) {
            nums[i] = Integer.parseInt(strs[i]);
        }
        //构建二叉树
        TreeNode root = buildTree(nums);

        //求二叉树最长路径
        int max = getMaxByList(root);
        System.out.println(max);


    }

    private static int getMaxByList(TreeNode root) {
        List<Integer> integers = longestPathsFromRoot(root);
        //求集合中的最大值
        int max = Integer.MIN_VALUE;
        for (Integer integer : integers) {
            if (integer > max) {
                max = integer;
            }
        }
        return max;
    }



    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }

    }

    public static TreeNode buildTree(int[] array) {
        return buildTreeHelper(array, 0);
    }

    private static TreeNode buildTreeHelper(int[] nums, int index) {
        if (index >= nums.length || nums[index] == -1) {
            return null;
        }
        TreeNode currentNode = new TreeNode(nums[index]);

        int leftChildIndex = 2 * index + 1;
        int rightChildIndex = 2 * index + 2;

        currentNode.left = buildTreeHelper(nums, leftChildIndex);
        currentNode.right = buildTreeHelper(nums, rightChildIndex);

        return currentNode;
    }


    public static List<Integer> longestPathsFromRoot(TreeNode root) {
        List<Integer> longestPathLengths = new ArrayList<>();
        dfs(root, new ArrayList<>(), longestPathLengths);
        return longestPathLengths;
    }

    private static void dfs(TreeNode node, List<Integer> currentPath, List<Integer> longestPathLengths) {
        if (node == null) {
            return;
        }
        currentPath.add(node.val);
        if (node.left == null && node.right == null) {
            longestPathLengths.add(sum(currentPath));
        } else {

            dfs(node.left, currentPath, longestPathLengths);
            dfs(node.right, currentPath, longestPathLengths);
        }


        currentPath.remove(currentPath.size() - 1);
    }

    private static int sum(List<Integer> path) {
        int sum = 0;
        for (int value : path) {
            sum += value;
        }
        return sum;
    }
}



